Magic bitboards - fast chess move generation

Magic bitboards

Definition

Magic bitboards are a fast, table-driven technique used in chess programming to generate sliding-piece attacks (rook, bishop, and queen) by mapping board occupancy to precomputed attack bitboards using a single multiplication and a shift. The “magic” refers to special 64-bit constants (magic numbers) that produce a perfect, collision-free index into an attack table.

How it works (high-level)

For each square and each sliding piece type, we precompute:

• A mask of the “relevant” squares along the rays from that square (excluding the edges).
• A magic multiplier and a right shift amount that, when applied to an occupancy subset, yields a unique index.
• An attack table containing, for every subset of relevant blockers, the resulting attack bitboard (all squares the piece could attack given those blockers).

At runtime, given the current board occupancy, we do:

(occupancy & mask) * magic >> shift → index

Then look up attacks[index] to get all attacked squares in O(1), with no loops along rays.

Usage in chess

Although “magic bitboards” is a programming term, the idea connects directly to chess concepts:

• Sliding piece attacks: Quickly compute rook/bishop/queen rays, including captures on the first blocker and stopping beyond it.
• Pins, x-rays, and discovered attacks: Efficiently re-evaluated during search when pieces move and lines open or close.
• Move generation and evaluation: Faster attack generation speeds up search depth, improving tactical accuracy and overall engine strength.

Why it’s called “magic”

The multipliers look like random 64-bit numbers, yet they “magically” map every possible occupancy subset to a unique small index (no collisions) via multiplication and shifting. These numbers are typically found by brute-force search offline or at program initialization.

Example (visualizing sliding attacks)

In the position below, White’s rook on d4 attacks along the rank and file until it meets the first blocker. Note how it can capture the black pawn on d5 and the black knight on h4, but it cannot move left because its own pawn on c4 blocks the way.

Rook rays are exactly what magic bitboards precompute and retrieve in a single table lookup.

Key ideas and terminology

• Bitboard: A 64-bit value where each bit corresponds to a square. Bitboard
• Relevant occupancy: For a given square, the set of squares along its rays that can contain blockers. Edge squares are excluded from the mask because the ray always stops there anyway.
• Perfect hashing: The magic number and shift create a unique mapping from each occupancy subset to an attack table entry.
• Attack bitboard: The bitboard of all squares a piece attacks given current blockers.

What gets precomputed

• Masks for each square and piece type (rook/bishop).
• Magic numbers and shifts (found via search).
• Attack tables:
  • Rook attacks table size is typically around 102,400 entries.
  • Bishop attacks table size is typically around 51,200 entries.
  • Each entry stores a 64-bit attack bitboard; total memory ~1.2 MB.
• Relevant bit counts:
  • Rooks: up to 14 bits from central squares (fewer on edges/corners).
  • Bishops: up to 13 bits from central squares (fewer on edges/corners).

Strategic and practical significance

For chess players, magic bitboards matter indirectly: faster, more efficient attack generation means engines can search more nodes per second. This extra speed translates into deeper and more accurate analysis, better finding of tactics, and stronger assistance in training and preparation. Many top engines, including Stockfish derivatives, rely on magic bitboards (or successors) for their speed.

Comparison with alternatives

• Rotated bitboards: An older approach using multiple rotated occupancy bitboards and bit scans. Magics are generally faster and simpler to maintain.
• PEXT-based attacks: On CPUs supporting BMI2, some engines use the hardware PEXT instruction to index attack tables even faster, with magics as a portable fallback.
• On-the-fly ray tracing: Simple but slower; iterating squares along each ray per move.

Interesting facts

• The technique became widely used in open-source engines in the mid-2000s and 2010s and is now a de facto standard for high-performance move generation.
• “Fancy” magics refer to tighter, high-quality magic numbers allowing smaller tables and fewer bits in the index.
• Good magic numbers look random but are carefully chosen to avoid collisions for the specific masks of each square.

Common pitfalls (implementation)

• Including edge squares in the mask (should be excluded).
• Not distinguishing own and enemy blockers when building attack bitboards (the first blocker is included only if it’s capturable).
• Incorrect shift or table sizing leading to collisions or out-of-bounds indices.
• Forgetting to regenerate tables if you change square indexing, bit-order, or occupancy conventions.

Related concepts

• Bitboard
• Sliding piece
• Rook and Bishop attacks
• Move generation
• Stockfish (many versions use magics or PEXT for attacks)

Summary

Magic bitboards are a clever, highly optimized way to compute rook and bishop attacks by hashing the occupancy of relevant squares into precomputed attack tables using a “magic” multiplication and shift. They replaced older techniques in many engines and remain a cornerstone of fast move generation, contributing directly to the strength and responsiveness of modern chess software.